package com.simon.study.algorithm.zheda;

import java.util.Arrays;
import lombok.Getter;
import lombok.Setter;

/**
 * <p>
 *
 * @author simon
 */
@Setter @Getter
public class Heap {

    int[]   elems;
    int     size;
    int     capacity;

    public Heap(int capacity) {
        this.capacity   = capacity;
        this.elems      = new int[this.capacity];
    }

    public boolean insert(int item){
        if(full()){ return false; }
        int idx = size++;

        while (item > elems[(idx-1)/2] && idx>0){
            elems[idx] = elems[(idx-1)/2];
            idx = (idx-1)/2;
        }
        elems[idx] = item;

        return true;
    }

    public int delete(){
        if(empty()){ return Integer.MIN_VALUE; }

        int index = 0, first = elems[index], left = (index<<1) + 1, tail  = elems[--size];

        while (left < this.size){
            if( left+1 < size && elems[left+1] > elems[left] ){ left++; }

            if( elems[left] < tail ){ break; }

            elems[index] = elems[left];

            index = left; left = (index<<1) + 1;
        }
        elems[index] = tail;
        return first;
    }



    public static void main(String[] args) {
        Heap heap = new Heap(30);

        /*
        // test insert
        int[] arr = new int[]{55,66,44,33,11,22,88,99,30,38,28,62};
        for (int i = 0; i < arr.length; i++) {
            heap.insert(arr[i]);
        }

        // see the tree from the heap
        Tree tree = new Tree();
        tree.setRoot(Tree.createFromMaxHeap(Arrays.copyOfRange(heap.elems, 0, heap.size)));
        tree.hiarachicallyPrint();

        int[] arr1 = new int[]{55,66,44,33,11,22,88,99,30,38,28,62};
        // see the tree from the original array.
        tree.setRoot(Tree.createMaxHeapTree(arr1));
        tree.hiarachicallyPrint();*/

        int[] arr = {88, 99, 56, 43, 78, 38};
        for (int i = 0; i < arr.length; i++) {
            heap.insert(arr[i]);
        }

        System.out.println(heap.toString());
        heap.delete();
        System.out.println(heap.toString());
    }


    public String toString(){
        int[] arr = Arrays.copyOf(this.elems, this.size);
        return Arrays.toString(arr);
    }

    public int getSize(){
        return this.size;
    }

    public boolean full(){
        return this.size == this.capacity;
    }

    public boolean empty(){
        return this.size == 0;
    }
}
